/**
 * 
 */
package algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.HashMap;


/**
 * @author neha & archana
 *  * This project is associated with the course COMS E6111. 
 * 
 * Group Members:
 * Neha Srivastava (ns2724)
 * Archana Balakrishnan (ab3416)
 * 
 * This project implements the apriori algorithm
 *
 */
public class apriori {

	/**
	 * @param args:
	 * args[0]= filename: for CSV data file
	 * args[1]: minimum support
	 * args[2]: minimum confidence 
	 */
	private static String filename;
	private static double MIN_SUP;
	private static double MIN_CONF;
	private static String outputFilename = "C:\\users\\ramaven\\documents\\output.txt";
	
	private static ArrayList<ArrayList<String>> transactions = new ArrayList<ArrayList<String>>();
	private static HashMap<ArrayList<String>,Double> minSupportForAllItemsets = new HashMap<ArrayList<String>,Double>();
	private static String outputString = "";
	
	

	//This function calculates the support of an itemset.
	public static double calcSupportforItemSet(ArrayList<String> itemset)
	{
		double support=0;
		boolean itemsetNotContained = false;
		
		
		for (ArrayList<String> t : transactions) {
			for (String item : itemset) {
				if (!t.contains(item)) {
					itemsetNotContained = true;
					break;
				}
			}
			
			if (itemsetNotContained == false) {
				support = support + 1;
			}
			
			itemsetNotContained = false;
		}
		
		
		
		support = support/transactions.size();
		
	
		
		return support;
	}
	
	
	//This function calculates the confidence of association rules LHS -> RHS.	
	public static double calcConfidence(ArrayList<String> LHS, String RHS)
	{
		/*
		 * Confidence of an association rule: support(LHS U RHS)/ support(LHS)
		 */
		
		double confidence=0;
		ArrayList<String> LHSRHS = new ArrayList<String>();
			Collections.sort(LHS);
			double supLHS = 0;
			double supLHSURHS = 0;
			
		
			if (minSupportForAllItemsets.containsKey(LHS))
				supLHS = minSupportForAllItemsets.get(LHS);
			
			for (String l : LHS)
				LHSRHS.add(l);
			LHSRHS.add(RHS);  // creating LHS U RHS
			Collections.sort(LHSRHS);
			
		
			if (minSupportForAllItemsets.containsKey(LHSRHS))
				supLHSURHS = minSupportForAllItemsets.get(LHSRHS);
			

			if (supLHS != 0)
				confidence= supLHSURHS/supLHS;
		
			return confidence;
	}
	
	//This function reads the input file and sets up the data.
	public static ArrayList<ArrayList<String>> readFileAndInitializeData(String strFile) {
		
		//Some lines in this function have been borrowed from the source code
		//at the following link - link - http://www.java-examples.com/parse-csv-file-using-stringtokenizer-example
		
		ArrayList<String> transaction;
		ArrayList<ArrayList<String>> transactions = new ArrayList<ArrayList<String>>();
		
		try
		{
			
			//create BufferedReader to read csv file
			BufferedReader br = new BufferedReader( new FileReader(strFile));
			String strLine = "";
			StringTokenizer st = null;
			int lineNumber = 0, tokenNumber = 0;
 
			//read comma separated file line by line
			while( (strLine = br.readLine()) != null)
			{
				lineNumber++;
 
				//break comma separated line using ","
				st = new StringTokenizer(strLine, ",");
				
				transaction = new ArrayList<String>();
				
				while(st.hasMoreTokens())
				{

					String item = new String();
					item = st.nextToken();
					item.trim();
					transaction.add(item);

					
				}
				
				transactions.add(transaction);
 
				//reset token number
				tokenNumber = 0;
 
			}
			
			
			int count = 1;
			for (ArrayList<String> i : transactions) { //i - each transaction consisting of a set of items
				count++;
				int countItem = 1;
				for (String d : i) {
					countItem++;
				}
			}
				
			
 
 
		}
		catch(Exception e)
		{
			System.out.println("Exception while reading csv file: " + e);			
		}
		
		
		return transactions;
	}
	
	
	
	//This function creates the 1-item sets L1.
	public static ArrayList<ArrayList<String>> createOneItemSets() {
		ArrayList<ArrayList<String>> alloneitemsets = new ArrayList<ArrayList<String>>();
		ArrayList<String> temp = new ArrayList<String>();
		ArrayList<String> allItems = new ArrayList<String>();
		

		for (ArrayList<String> itemset : transactions) {
			for (String item : itemset) {
				temp = new ArrayList<String>();
				if (!allItems.contains(item)) {
					temp.add(item);
					allItems.add(item);
					alloneitemsets.add(temp);
				}
			}
		}
	
		
	

		
		
		//Removing the transactions with support < min_support from L1
		
		ArrayList<ArrayList<String>> L1 = new ArrayList<ArrayList<String>>();
		
		for (ArrayList<String> itemset : alloneitemsets) {
			if (calcSupportforItemSet(itemset) >= MIN_SUP) {
				L1.add(itemset);
			}
		}
		
		
		return L1;
	}
	
	
	//This function joins two k-1 item sets to produce one k-item set.
	public static ArrayList<ArrayList<String>> aprioriGenerator(ArrayList<ArrayList<String>> LkMinus1) {
		ArrayList<ArrayList<String>> Ck = new ArrayList<ArrayList<String>>();
		ArrayList<String> kItemset;
		
		boolean canJoin = true;
		
		for (ArrayList<String> outer : LkMinus1) {
			
			for (ArrayList<String> inner : LkMinus1) {
				kItemset = new ArrayList<String>(); //reset kItemset
				for (String o: outer)
				
				for (String i: inner)
	
				
				
				canJoin = compareItemsets(outer, inner); //comparing Lk with Lk
					

					
					if (canJoin == true) {
						for (String o : outer) {
							kItemset.add(o);
						}
						
						kItemset.add(inner.get(inner.size()-1));
						
						
						Ck.add(kItemset); //add the itemset to the list of candidate large 
										  //itemsets
					}
					
			}
		
		}
		
		Ck = pruneCandidates(Ck, LkMinus1);
		
		return Ck;
	}
	
	//This function prunes the candidate set Ck by removing k-1 subsets not in Lk-1.
	public static ArrayList<ArrayList<String>> pruneCandidates(ArrayList<ArrayList<String>> Ck, ArrayList<ArrayList<String>> LkMinus1) {
	
		CombinationGenerator subsetGenerator;
		int[] indices;
		ArrayList<ArrayList<String>> itemSetsMarkedDeleted = new ArrayList<ArrayList<String>>();
		ArrayList<String> subset = new ArrayList<String>(); 
		
		for (ArrayList<String> itemset : Ck) {
			subsetGenerator = new CombinationGenerator(itemset.size(), itemset.size() - 1);
			
			
			for (String item : itemset) {
			}
			
			while(subsetGenerator.hasMore())
			{
				subset.clear();
				indices= subsetGenerator.getNext();
				for(int i=0; i<indices.length; i++)
				{
					subset.add(itemset.get(indices[i]));
					

					
					if (!LkMinus1.contains(subset))
						itemSetsMarkedDeleted.add(subset);
						
					
				}
			}
			
		}
		
		
		
		
		
		
		return Ck;
	}
	
	
	//This function determines whether two Lk-1 itemsets can be joined to produce an Lk itemset.
	public static boolean compareItemsets(ArrayList<String> outer, ArrayList<String> inner) {
		boolean canJoin = false;
		

		
		//if the last item of the itemsets are the same, return false
		//They may even be the same itemset!
		if (inner.get(outer.size()-1)== outer.get(outer.size()-1)) {
			canJoin = false;
			return canJoin;
		}
		
		
		
		for (int i = 0; i < outer.size(); i++) { //outer.size - size of the itemset
			//if any item except the last item is different between the item sets,
			//return false
			if (i < outer.size()-1) {
				if (inner.get(i) != outer.get(i)) {
					canJoin = false;
					return canJoin;
				}	
			}
			
			else if (outer.get(i).compareTo(inner.get(i)) < 0){
				//last item cannot be the same because they have already been removed
				//last item of the outer string must be less than the last item of
				//the inner string - this condition removes duplicate matches
				canJoin = true;
			}
		}
		
		
		return canJoin;
	}
	
	//This function generates the subsets of each itemset in the list of candidate itemsets Ck
	//and calculates minsupport.
	public static ArrayList<ArrayList<String>> generateCtAndCalcMinSupport(ArrayList<ArrayList<String>> Ck) {
		ArrayList<ArrayList<String>> Ct = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> subsets = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> temp;
		 
		
		for (ArrayList<String> itemset : Ck) {
			
			temp = new ArrayList<ArrayList<String>>();
			
			for (int i = 0; i < itemset.size(); i++) {
				temp = generateSubsets(itemset, i+1);
				
				for (ArrayList<String> ss : temp) {
					
					if (!subsets.contains(ss)) {

						subsets.add(ss);
						double minSupport = calcSupportforItemSet(ss);
						 
						Collections.sort(ss);
						if (minSupportForAllItemsets.containsKey(ss) == false) { 
							minSupportForAllItemsets.put(ss, minSupport);
						}
				}
			}
			
			
				
		}
		
		}
		
		return Ct;
	}
	
	
	//Given an itemset and the size of the reqd. subset (say l), this function returns
	//all the l-sized subsets of itemset.
	public static ArrayList<ArrayList<String>> generateSubsets(ArrayList<String> itemset, int subsetSize) {
		ArrayList<ArrayList<String>> subsets = new ArrayList<ArrayList<String>>();
		CombinationGenerator subsetGenerator = new CombinationGenerator(itemset.size(), subsetSize);
		ArrayList<String> subset = new ArrayList<String>();
		int[] indices;
		
		while(subsetGenerator.hasMore())
		{
			subset = new ArrayList<String>();
			indices= subsetGenerator.getNext();
			for(int i=0; i<indices.length; i++)
			{
				subset.add(itemset.get(indices[i]));
				
	
			}

			subsets.add(subset);
			
		}
		
		
		return subsets;
	}
	
	//filter all candidates that have minsupport < MIN_SUP
	public static ArrayList<ArrayList<String>> generateLk(ArrayList<ArrayList<String>> Ck) {
		ArrayList<ArrayList<String>> Lk = new ArrayList<ArrayList<String>>();
		double support;
		
		for (ArrayList<String> itemset : Ck) {
			if (minSupportForAllItemsets.containsKey(itemset)) {
				support = minSupportForAllItemsets.get(itemset);
				if (support >= MIN_SUP) {
					Lk.add(itemset);
				}
				
					
			}
		}
		
		Lk = sortLk(Lk);
		return Lk;
	}
	
	
	//sorts each itemset of Lk lexicographically
	public static ArrayList<ArrayList<String>> sortLk(ArrayList<ArrayList<String>> Lk) {
		
		for (ArrayList<String> itemset : Lk) {
			Collections.sort(itemset);
		}
		

		
		
		return Lk;
	}
	
	//This function creates the association rules and calculates confidence.
	public static void createAssociationRules(ArrayList<ArrayList<String>> Lk) {
		//argument - itemsets that have support and confidence greater than threshold values
		ArrayList<String> LHS = new ArrayList<String>();
		double support = 0;
		ArrayList<String> LHSURHS = new ArrayList<String>();
		
		ArrayList<ArrayList<String>> RHSSubsets = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> mMinus1Subsets = new ArrayList<ArrayList<String>>();
		
		double confidence;
		
		for (ArrayList<String> itemset : Lk) {
			LHS = new ArrayList<String>();
			LHSURHS = new ArrayList<String>();
			
			Collections.sort(itemset);

				RHSSubsets = generateSubsets(itemset, 1); 
				//generating 1-item sets for RHS  
				
				for (ArrayList<String> RHSSubset : RHSSubsets) { //RHSSubset is a 1-item list
					
					LHS = new ArrayList<String>();
					LHSURHS = new ArrayList<String>();
					
					for (String RHS : RHSSubset) { //loop runs once
						LHS = new ArrayList<String>();
					
				
	
					LHS = allButRHS(itemset, RHS);
				
					
					confidence = calcConfidence(LHS, RHS);
				
					if (confidence > MIN_CONF) {
						
						for (String l : LHS) {
							LHSURHS.add(l);
						}
						
						LHSURHS.add(RHS);
						
						Collections.sort(LHSURHS); //item sets stored in hashmap in sorted order
						
						
						if (minSupportForAllItemsets.containsKey(LHSURHS))
							support = minSupportForAllItemsets.get(LHSURHS);
						
						String lstr = "";
						int countComma = 0;
						
						for (String l : LHS) {
							lstr += l;
							if (countComma != LHS.size()-1)
								lstr += ",";
							countComma++;
							
						}
						
						
						
						
						outputString += "[" + lstr.trim() + "] => [" + RHS.trim() + "]";
						outputString += "(Conf: " + confidence*100 + "%, Supp: " + support*100 + "%)";
						outputString += (char) 13;
				
				
					}
					}
				}
				
		}
		
	}
	
	
	
	
	//This function computes the LHS of an association rule.
	public static ArrayList<String> allButRHS(ArrayList<String> itemset, String RHS) {
		ArrayList<String> temp = new ArrayList<String>();
		
		for (String i : itemset)
			temp.add(i);
			
		temp.remove(RHS);
		
		return temp;
	}
	
	
	//This function is called to write the output string to the output file.
	public static void writeToFile(String filename, String value) {
        
        BufferedWriter bufferedWriter = null;
        
        try {
            
            //Construct the BufferedWriter object
            bufferedWriter = new BufferedWriter(new FileWriter(filename));
            
            //Start writing to the output stream
            bufferedWriter.append(value);
            bufferedWriter.newLine();
            
        } catch (FileNotFoundException ex) {
            ex.printStackTrace();
        } catch (IOException ex) {
            ex.printStackTrace();
        } finally {
            //Close the BufferedWriter
            try {
                if (bufferedWriter != null) {
                    bufferedWriter.flush();
                    bufferedWriter.close();
                }
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }
	
	//This function prepares the output string for the support section of the output file.
	public static void writeSupportValuesToOutputFile(ArrayList<ArrayList<String>> Lk) {
		
		String temp = "";
		double support = 0;
		int countComma = 0;
		
		for (ArrayList<String> itemset : Lk) {
			countComma = 0;
			Collections.sort(itemset);
			temp += "[";
			for (String item : itemset) {

				temp += item.trim();
				
				if (countComma != itemset.size()-1) {
					temp += ",";
				}
				
				countComma++;
			}
			
	
			temp += "],";
			
			
			if (minSupportForAllItemsets.containsKey(itemset))
				support = minSupportForAllItemsets.get(itemset);
			
			temp += (support*100) + "%" + (char) 13; 
			
		}
		
		outputString += temp;
	}
	
	public static void main(String[] args) {
		
			
		ArrayList<ArrayList<String>> LkMinus1 = null;
		ArrayList<ArrayList<String>> Ck = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> Ct = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> Lk = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> associationRules = new ArrayList<ArrayList<String>>();
		
		filename=args[0];
		MIN_SUP= Double.parseDouble(args[1]);
		MIN_CONF= Double.parseDouble(args[2]);
		
		ArrayList<ArrayList<ArrayList<String>>> LK = new ArrayList<ArrayList<ArrayList<String>>>();
		
	
		transactions = readFileAndInitializeData(filename);
		
		//L1 - one-item sets
		ArrayList<ArrayList<String>> L1 = createOneItemSets();
		
		
		System.out.println("All one-item sets: ");
		
		//Printing all one-item sets
		for (ArrayList<String> itemset : L1) {
			for (String i: itemset) {
				System.out.println(i);
			}
		}
		
		
		LK.add(L1); //Note L1 is stored at LK[0] = LK[k-1]
		LkMinus1 = L1;
		
				
		
		for (int k = 2; LkMinus1.isEmpty() == false; k++) {
			Ck = aprioriGenerator(LkMinus1);
			Ct = generateCtAndCalcMinSupport(Ck);
			Lk = generateLk(Ck);
			LK.add(Lk); //Note Lk is stored at LK[k-1]
			

			
			LkMinus1 = Lk;
			
		}
		
		
		
		System.out.println("Creating output string for support...");

		//Preparing o/p string for support section of o/p file
		outputString += "==Large itemsets (min_sup=" + MIN_SUP*100 + "%)" + (char) 13;
		
		for(int k = 1; k<=LK.size(); k++) {
			writeSupportValuesToOutputFile(LK.get(k-1));
		}
		
		outputString += "==High-confidence association rules (min_conf=" + MIN_CONF*100 + "%)";
		outputString += (char) 13;
		
		
		System.out.println("Creating output string for confidence...");
		
		//Preparing o/p string for confidence section of o/p file
		for(int k = 2; k<=LK.size(); k++) {
			createAssociationRules(LK.get(k-1));
		}
		
		System.out.println("Writing to output file...");
		writeToFile(outputFilename, outputString);
		System.out.println("Done writing to output file!!!");
		
		
		
	}

}
